import javax.management.NotificationFilterSupport;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by L.jp
 * Description:输入一棵二叉树的根节点，求该树的深度。
 * 从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
 * User: 86189
 * Date: 2023-02-01
 * Time: 23:20
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Solution {
    //递归，dfs,二叉树的深度就是二叉树左右子树高度的最大值+1
   /* public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }*/
    
    //非递归，就是bfs,使用层序遍历，就是队列存储每一层的元素
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        Queue<TreeNode> bfsQueue=new LinkedList<>();
        bfsQueue.offer(root);
        int res=0;
        while (!bfsQueue.isEmpty()){
            int size=bfsQueue.size();
            //队列里存储的是当前层的节点
            while (size>0){
                TreeNode tmp=bfsQueue.poll();
                if(tmp.left!=null){
                    bfsQueue.offer(tmp.left);
                }
                if(tmp.right!=null){
                    bfsQueue.offer(tmp.right);
                }
                //队列的大小减少,上一层的节点数
                size--;
            }
            //当前层的节点遍历完毕
            res++;
        }
        return res;
    }
}
